package LeetCodeHot100TopInterview;

public class Q070_ClimbStairs {

    //爬楼梯
    //一步两步问几种方式
    //同剑指offerQ10—2青蛙跳台阶
    public int climbStairs(int n) {
        if (n < 2){
            return n == 1? 1: 0;
        }
        int[] dp = new int[n + 1];
        // 0 --> n
        dp[n] = 1;
        dp[n - 1] = 1;
        dp[n - 2] = 2;
        for (int i = n - 3; i > -1 ; i--) {
            dp[i] = dp[i + 1] + dp[i + 2];
        }
        return dp[0];
    }

    public static void main(String[] args) {
        Q070_ClimbStairs fun = new Q070_ClimbStairs();
        System.out.println(fun.climbStairs(3));
    }
}
